home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 288_01 / 3opt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  3.0 KB  |  83 lines
  1. /*
  2.         HEADER:         CUG000.05;
  3.         TITLE:          ThreeOpt;
  4.         DATE:           Mar 89;
  5.         DESCRIPTION:    3-Opt Tour Improvement Algorithm;
  6.         VERSION:        2.0;
  7.         FILENAME:       3OPT.C;
  8.         SEE-ALSO:       TSP.C, NN.C, POPT.C, 2OPT.C, HYBRID.C, FN.C,
  9.                         BOOLEAN.H, NODELIST.H, TSP.H,
  10.                         BLDMTX.C, PRTMTX.C, TIME.C;
  11.         AUTHORS:        Kevin E. Knauss;
  12. */
  13.  
  14. #include <nodelist.h>
  15.  
  16. long ThreeOpt (NumberOfVirteces, Path)
  17.    unsigned NumberOfVirteces;
  18.    NODE *Path;
  19. {
  20.    unsigned ArcCost();
  21.    long CircuitCost;
  22.    unsigned count, index, pindex, sindex, j, k;
  23.    unsigned D1, D2, D3, D4;
  24.    NODE *First, *Last, *Kth, *Jth, *Save, *Reverse;
  25.  
  26.    count = 1;
  27.    First = Path;
  28.    do {
  29.       Last = First->prior;
  30.       Kth = First->next;
  31.       /* when j = k+1, D1 checks k=1 case (i.e. single point) */
  32.       do {
  33.          Jth = Kth->next;
  34.          /* when j = k+1, D2 checks 2-Opt */
  35.          do {
  36.             D1 = ArcCost (Kth->position, Jth->next->position)
  37.                + ArcCost (First->position, Jth->position);
  38.             D2 = ArcCost (First->position, Jth->next->position)
  39.                + ArcCost (Kth->position, Jth->position);
  40.             D3 = ArcCost (Kth->next->position, Last->position);
  41.             D4 = ArcCost (First->position, Last->position)
  42.                + ArcCost (Kth->position, Kth->next->position)
  43.                + ArcCost (Jth->position, Jth->next->position);
  44.             if (((D1 + D3) < D4) || ((D2 + D3) < D4)) {
  45.                Last->next = Kth->next;
  46.                Kth->next->prior = Last;
  47.                if (D1 <= D2) {
  48.                   Kth->next = Jth->next;
  49.                   Kth->next->prior = Kth;
  50.                   Jth->next = First;
  51.                   First->prior = Jth;
  52.                } else {
  53.                   for ( Reverse = First; Reverse != Kth; Reverse = Save) {
  54.                      Save = Reverse->next;
  55.                      Reverse->next = Reverse->prior;
  56.                      Reverse->prior = Save;
  57.                   }
  58.                   First->next = Jth->next;
  59.                   Jth->next->prior = First;
  60.                   Kth->next = Kth->prior;
  61.                   Kth->prior = Jth;
  62.                   Jth->next = Kth;
  63.                }
  64.                count = 0;
  65.                First = Last->next;
  66.                Kth = First->next;
  67.                Jth = Kth->next;
  68.             } else
  69.                Jth = Jth->next;
  70.          } while ((Jth != Last->prior) && (count != 0));
  71.          Kth = Kth->next;
  72.       } while ((Kth != Last->prior->prior->prior) && (count != 0));
  73.       if (count != 0)
  74.          First = First->next;
  75.       count++;
  76.    } while (count < NumberOfVirteces);
  77.    Last = First->prior;
  78.    CircuitCost = ArcCost (Last->position, First->position);
  79.    for ( Kth = First; Kth != Last; Kth = Kth->next)
  80.       CircuitCost += ArcCost (Kth->position, Kth->next->position);
  81.    return (CircuitCost);
  82. } /* ThreeOpt */
  83.